package com.zhz.leetcode;

import com.zhz.leetcode.entity.ListNode;
import com.zhz.leetcode.utils.LinkedListUtils;

import java.util.ArrayList;

/**
 * 19. 删除链表的倒数第 N 个结点
 * 给你一个链表，删除链表的倒数第n个结点，并且返回链表的头结点。
 * <p>
 * 示例 1：
 * 输入：head = [1,2,3,4,5], n = 2
 * 输出：[1,2,3,5]
 * <p>
 * 示例 2：
 * 输入：head = [1], n = 1
 * 输出：[]
 * <p>
 * 示例 3：
 * 输入：head = [1,2], n = 1
 * 输出：[1]
 * <p>
 * 提示：
 * <p>
 * 链表中结点的数目为 sz
 * 1 <= sz <= 30
 * 0 <= Node.val <= 100
 * 1 <= n <= sz
 * <p>
 * <p>
 * 进阶：你能尝试使用一趟扫描实现吗？
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class RemoveNthNodeFromEndOfList19 {

    public static void main(String[] args) {
        RemoveNthNodeFromEndOfList19 m = new RemoveNthNodeFromEndOfList19();
        ArrayList<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        ListNode node = LinkedListUtils.createListNode(list);
        ListNode head = m.removeNthFromEnd(node, 3);
        LinkedListUtils.printList(head);
    }

    /**
     * 删除倒数第n个元素，然后再返回数据
     * 思路：先找到第N个元素，然后操作当前元素，将其val和next值改掉
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head.next == null) {
            return null;
        }
        ListNode curr = head;
        ArrayList<ListNode> list = new ArrayList<>();
        while (curr != null) {
            list.add(curr);
            curr = curr.next;
        }
        if (n > list.size()) {
            return head;
        }
        curr = list.get(list.size() - n);
        if (curr.next != null) {
            curr.val = curr.next.val;
            curr.next = curr.next.next;
        } else {//如果没有next，则需要移除当前
            ListNode prev = list.get(list.size() - 2);
            prev.next = null;
        }
        return head;
    }

}
